// https://www.lintcode.com/problem/binary-tree-path-sum/description?_from=ladder&&fromId=6

/**
 * Definition of TreeNode:
 * class TreeNode {
 * public:
 *     int val;
 *     TreeNode *left, *right;
 *     TreeNode(int val) {
 *         this->val = val;
 *         this->left = this->right = NULL;
 *     }
 * }
 */


class Solution {
public:
    /*
     * @param root: the root of binary tree
     * @param target: An integer
     * @return: all valid paths
     */
    void count_sum (TreeNode * root, int target, vector<vector<int>>& result, vector<int>& tmp)
    // void count_sum (TreeNode * root, int target, vector<vector<int>>& result, vector<int> tmp)
    { 
        if (!root) return;
        tmp.push_back(root->val);
        if (!root->left && !root->right) 
        {
            if (root->val == target)
            {
                result.push_back(tmp);
            }
        }
        count_sum (root->left, target - root->val, result, tmp);
        count_sum (root->right, target - root->val, result, tmp);
        // tmp.pop_back();
    }
    vector<vector<int>> binaryTreePathSum(TreeNode * root, int target) {
        vector<vector<int>> result;
        vector<int> tmp;
        count_sum(root, target, result, tmp);
        return result;
    }
};

// https://leetcode.cn/problems/path-sum/submissions/
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */

class Solution {
public:
    bool dfs(TreeNode* root, int targetSum, int sum) {
        if (!root) return false;
        int tmp = root->val;
        if (!root->left && !root->right) return sum + tmp == targetSum;
        return dfs(root->left, targetSum, sum + tmp) || dfs(root->right, targetSum, sum + tmp);
    }
    bool hasPathSum(TreeNode* root, int targetSum) {
        return dfs(root, targetSum, 0);
    }
};

class Solution {
public:
    bool hasPathSum(TreeNode* root, int targetSum) {
        if (!root) return false;
        if (!root->left && !root->right) return root->val == targetSum;
        return hasPathSum(root->left, targetSum - root->val) || hasPathSum(root->right, targetSum - root->val);
    }
};